Between 1998 and 2004, the planning community has seen vast progress in termsof the sizes of benchmark examples that domain-independent planners can tacklesuccessfully. The key technique behind this progress is the use of heuristicfunctions based on relaxing the planning task at hand, where the relaxation isto assume that all delete lists are empty. The unprecedented success of suchmethods, in many commonly used benchmark examples, calls for an understandingof what classes of domains these methods are well suited for. In theinvestigation at hand, we derive a formal background to such an understanding.We perform a case study covering a range of 30 commonly used STRIPS and ADLbenchmark domains, including all examples used in the first four internationalplanning competitions. We *prove* connections between domain structure andlocal search topology -- heuristic cost surface properties -- under anidealized version of the heuristic functions used in modern planners. Theidealized heuristic function is called h^+, and differs from the practicallyused functions in that it returns the length of an *optimal* relaxed plan,which is NP-hard to compute. We identify several key characteristics of thetopology under h^+, concerning the existence/non-existence of unrecognized deadends, as well as the existence/non-existence of constant upper bounds on thedifficulty of escaping local minima and benches. These distinctions divide the(set of all) planning domains into a taxonomy of classes of varying h^+topology. As it turns out, many of the 30 investigated domains lie in classeswith a relatively easy topology. Most particularly, 12 of the domains lie inclasses where FFs search algorithm, provided with h^+, is a polynomial solvingmechanism. We also present results relating h^+ to its approximation asimplemented in FF. The behavior regarding dead ends is provably the same. Wesummarize the results of an empirical investigation showing that, in manydomains, the topological qualities of h^+ are largely inherited by theapproximation. The overall investigation gives a rare example of a successfulanalysis of the connections between typical-case problem structure, and searchperformance. The theoretical investigation also gives hints on how thetopological phenomena might be automatically recognizable by domain analysistechniques. We outline some preliminary steps we made into that direction.
展开▼
